package demo4;

//牛客网:字符串重排列

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
     ArrayList<String> ret = new ArrayList<>();
     int n;
     String s;
     int[] st = new int[26];
     Set<String> set = new HashSet<>();
    public ArrayList<String> Permutation (String str) {
        // write code here
        n = str.length();
        s = str;
        for(int i = 0; i<n; i++) {
            st[str.charAt(i)-'a']++;
        }
        dfs(new StringBuffer(""));
        return ret;
    }
    public void dfs(StringBuffer u) {
        if(u.length() == n) {
            String str = new String(u);
            if(!set.contains(str)) {
                ret.add(str);
                set.add(str);
            }
            return;
        }

        for(int i = 0; i<n; i++) {
            char ch = s.charAt(i);
            if(st[ch-'a']>0) {
                st[ch-'a'] --;
                dfs(u.append(ch));
                u.deleteCharAt(u.length()-1);
                st[ch-'a'] ++;
            }
        }
    }
}